

// 完全背包问题
public class KnapsackProblemComplete {
    static class Item {
        int index;
        String name;
        int weight;
        int value;

        public Item(int index, String name, int weight, int value) {
            this.index = index;
            this.name = name;
            this.weight = weight;
            this.value = value;
        }

        @Override
        public String toString() {
            return "Item(" + name + ")";
        }
    }

    public static void main(String[] args) {
        Item[] items = new Item[]{
                new Item(1, "青铜", 2, 3),    // c
                new Item(2, "白银", 3, 4),    // s
                new Item(3, "黄金", 4, 7),    // a
        };
        System.out.println(select1(items, 6));
    }

    // 二维数组实现
    private static int select(Item[] items, int total){
        int[][] dp = new int[items.length][total + 1];
        Item item = items[0];
        for (int j = 0; j < total + 1; j++){
            if (j >= item.weight){
                dp[0][j] = dp[0][j - item.weight] + item.value;
            }
        }
        for (int i = 1; i < items.length; i++){
            Item item1 = items[i];
            for (int j = 1; j < total + 1; j++){
                if (j >= item1.weight){
                    dp[i][j] = Integer.max(dp[i - 1][j], dp[i][j - item1.weight] + item1.value);
                }else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[dp.length - 1][total];
    }

    // 一维数组实现
    private static int select1(Item[] items, int total){
        int[] dp = new int[total + 1];
        Item item = items[0];
        for (int j = 0; j < total + 1; j++){
            if (j >= item.weight){
                dp[j] = dp[j - item.weight] + item.value;
            }
        }
        for (int i = 1; i < items.length; i++){
            Item item1 = items[i];
            for (int j = 1; j < total + 1; j++){
                if (j >= item1.weight){
                    dp[j] = Integer.max(dp[j], dp[j - item1.weight] + item1.value);
                }
            }
        }
        return dp[total];
    }
}
